home *** CD-ROM | disk | FTP | other *** search
/ Chip 1996 April / CHIP 1996 aprilis (CD06).zip / CHIP_CD06.ISO / hypertxt.arj / 9508 / E_MESSZE.CD < prev    next >
Text File  |  1996-03-10  |  8KB  |  149 lines
  1.           @VRejtvénymegfejtés@N
  2.  
  3.           @VAutózzunk...@N
  4.  
  5.               ..minél messzebbre címmel jelent meg áprilisi számunkban
  6.           fejtörônk.  Az alábbiakban a megoldásokat közöljük.
  7.               A  feladat:  a  lehetô  legtávolabbra  kellene eljutnunk
  8.           üzemanyagbázisunkról 50 literes benzintankú autónkkal, amely
  9.           100  km-enként  10  liter  benzint  fogyaszt,  és induláskor
  10.           tankja tele  van. A  bázison @KN@N  darab 200  literes hordó áll
  11.           rendelkezésünkre, tele benzinnel, azonban egyszerre csak egy
  12.           hordót   tudunk    magunkkal   vinni,    függetlenül   annak
  13.           telítettségi fokától.
  14.               A rejtvényre hat megfejtés érkezett, különféle formákban
  15.           és úton.  A hagyományos  levél, illetve  lemez mellett  nagy
  16.           örömünkre már kaptunk megfejtéseket e-mailen is. A Pascal--C
  17.           verseny  jelenleg  döntetlenre áll,  s  ráadásként (Bonifert
  18.           Csaba jóvoltából) feltûnt  egy új nyelv  is, a Linux  alatti
  19.           Common Lisp.
  20.               Megfejtôink   többsége  (5:1   arányban)  lényegében   a
  21.           következô gondolatmenet szerint okoskodott (Barczikay Zsolt,
  22.           illetve  Pittner Ferenc  dokumentációja alapján).  Barczikay
  23.           Zsolt:  ""Természetesen  fel  kell  használnunk  az   összes
  24.           benzint,  hogy  legtávolabb  juthassunk,  ehhez  viszont  az
  25.           összes   hordót   ki  kell   ürítenünk.   Az  összes   hordó
  26.           elôreviteléhez   folyton   oda-vissza   kell  szaladgálnunk.
  27.           Legcélszerûbb kiválasztani egy akkora távolságot,  amekkorán
  28.           egy tanknyi benzinnel  átvihetjük minden hordónkat.  @KN@N hordó
  29.           esetén @K2*N-1@N-szer  kell megtennünk  ezt a  távot, amely  így
  30.           @K500/(2*N-1)@N-nek adódik. Ekkor tankolunk, majd ismételjük  az
  31.           eljárást. Természetesen tankolás után ellenôrizzük, hogy nem
  32.           ürült-e ki valamelyik hordó,  hiszen azt ekkor már  nem kell
  33.           cipelnünk.  Amikor  már  csak  egy  hordónk  marad  (és tele
  34.           tankunk) akkor  még 2500  km-t tudunk  menni." Olvasónk ezen
  35.           algoritmus  alapján  mintegy  szimulálta  az  utat.  Pittner
  36.           Ferenc matematikai összefüggést állított fel a hordók  száma
  37.           és a megtett út között.
  38.               Olvasónk   (s   még    Varga   József,   Tóth    László)
  39.           végeredményben  ezen  képlet  kiszámítására  írt  programot.
  40.           Eredményeik  1, 2,  3, 10  hordóra 2500,  3166,67,  3566,67,
  41.           4766,51 km.
  42.               Egészen más gondolatmenetet  követett Bonifert Csaba.  ï
  43.           nem  tartotta  szükségesnek  a  hordók  ""egyszerre" történô
  44.           mozgatását, illetve a minden @KN@N-re az azonos  ""menetrendet".
  45.           îgy a  fenti hordószámokra  a következô  távolságokat kapta:
  46.           2500, 3083,3  (ami biztosan  nem optimális),  3633,3, 5046,6
  47.           (amik lehetnek optimálisak). ""A megoldás durva  algoritmusa
  48.           -- írja levelében --:
  49.               1. Jelöljünk ki egy új állomást az aktuális állomástól B
  50.           távolságra (B<=500).
  51.               2.  Amennyi  hordót  csak  tudunk,  vigyünk  át  az   új
  52.           állomásra.
  53.               3. Ha már  csak egy hordónk  van, menjünk addig,  amíg a
  54.           benzinünk el nem fogy.
  55.               4. Egyébként folytassuk az 1. lépéssel.
  56.               Az algoritmusban gyakorlatilag két lépést ismételgetünk:
  57.           az  aktuális  állomásról egy  hordót  átviszünk a  következô
  58.           állomásra, illetve visszamegyünk egy állomást, hordó nélkül.
  59.           A fô probléma, hogy milyen távolságra legyen az új  állomás.
  60.           Åltalában igaz, hogy az állomasok közötti távolság nem lehet
  61.           nagyobb  500  km-nél, mert  akkor  nem tudnánk  visszamenni.
  62.           Addig mindegy az új állomás távolsága, amíg közben nem  ürül
  63.           ki hordó, vagy nem csappan meg annyira a tartalma, hogy  már
  64.           nem érdemes visszamenni érte.
  65.               Tegyük fel, hogy az @KA(x)@N állomáson @KK@N db tele hordó és az
  66.           autó  tankjában  @KT@N  benzin van.  ùgy  kell  megválasztani az
  67.           @KA(x+1)@N állomás távolságát, hogy:
  68.               -- mindig tele hordókat vigyünk át A(x+1)-re;
  69.               --  visszainduláskor  ne  kelljen  az  átvitt   hordóból
  70.           tankolnunk;
  71.               -- az utolsó hordó átvitelénél induláskor az autó tankja
  72.           tele legyen;
  73.               -- a szállítás teljes benzinigényét pontosan fedezze  az
  74.           egy darab A(x)-on maradt hordó.
  75.               E  négy feltételbôl  következik, hogy  @KK-1@N darab  hordót
  76.           viszünk át, összesen @K2*(K-2)@N-szer tesszük meg a két  állomás
  77.           közötti távot, tehát fennáll az alábbi összefüggés:
  78.               @KK*200+T=(K-1)*200+2*(K-2)*B+50@N
  79.               (Az utolsó induláskor tele a tank, ez a + 50 liter, @KB@N  a
  80.           két állomás távolsága literben.) Az egyenletbôl:
  81.               @KB=(150+T)/(2*K-4)@N
  82.               Tehát így  kell(ene) megválasztani  a következô  állomás
  83.           távolságát, de ez  az összefüggés csak  5 tele hordó  fölött
  84.           használható, mert @KB@N maximum 25 liter lehet, hogy ne  kelljen
  85.           visszafele  tankolni  az  átvitt  hordóból.  Ezért  öt  vagy
  86.           kevesebb hordó  esetén más  megoldást kell  keresni, melynek
  87.           lényege, hogy  a két  fenti lépés  közé be  kell iktatni egy
  88.           (vagy több)  olyan szállítást,  amikor nem  csökken a hordók
  89.           száma."  A  megoldás  részletei  kiolvashatók  megfejtônk  C
  90.           nyelvû  programjából,  mely  a  CT  BBS-en  megtalálható.  A
  91.           BBS-hez hozzá nem férôk számára  álljon itt az @KN=3@N eset  egy
  92.           lehetséges ""aprópénzre váltása":
  93.               1. 1. hordót 250 km-re elvisszük (S1 segéd-állomás).
  94.               2. Tankot feltöltjük H1-bôl (H1=175).
  95.               3. Vissza a bázisra.
  96.               4. 2. hordót S1-re visszük.
  97.               5. Tankot feltöltjük H1-bôl (H1=125).
  98.               6. Vissza a bázisra.
  99.               7. 3. hordó S1-re.
  100.               8. Tankot feltöltjük H1-bôl (H1=75).
  101.               9. 2. hordót  elôre 50 km-rel  (A1 állomás, távolsága  a
  102.           bázistól 300 km).
  103.               10. Vissza S1-re.
  104.               11. 3. hordót A1-re.
  105.               12. Vissza S1-re.
  106.               13. 1. hordót A1-re.
  107.               14. Tankot feltöltjük H1-bôl (H1=50, T=50).
  108.               15. 2.  hordót elôre  250 km-rel  (A2 állomás, távolsága
  109.           A1-tôl 250 km).
  110.               16. Vissza A1-re.
  111.               17. Tankot feltöltjük H1-bôl (H1=0!).
  112.               18. 3. hordót elôre 500 km-t (S2 állomás).
  113.               19. Tankot feltöltjük H3-bôl (H3=150).
  114.               20. Vissza A2-re.
  115.               21. 2. hordót S2-re.
  116.               22. Tankot feltöltjük H3-bôl (H3=100).
  117.               23. 2. hordót 250 km-rel elôre (S3 állomás).
  118.               24. Vissza S2-re.
  119.               25. Tankot feltöltjük H3-bôl (H1=50).
  120.               26. 3. hordót S3-re.
  121.               27. 2. hordót elôre  83.333 km-t (A3 állomás,  távolsága
  122.           A2-tôl 583,3 km).
  123.               28. Vissza S3-ra.
  124.               29. 3. hordót A3-ra.
  125.               30. Tankot feltöltjük H3-bôl (H3=0, T=50, H2=200).
  126.               31. Innen 2500 km tehetô meg.
  127.               Tehát az összes út 300+250+583,3+2500=3633,3 km.
  128.               A hónap nyertese Bonifert Csaba, most kivételesen nem  a
  129.           szerencse, hanem a távolság okán.
  130.  
  131.           @VBánhegyesi Zoltán@N
  132.  
  133.  
  134.           @Vùj rejtvényünk@N
  135.  
  136.           @VIsmét hordók@N
  137.  
  138.               A feladat ""körítése" hasonló áprilisi  rejtvényünkéhez,
  139.           de  a  feltételek  mások.  Egy  körút  mentén  hordók vannak
  140.           elhelyezve tetszôlegesen, különbözô mennyiségû (de  nullánál
  141.           több)   benzinnel,   de   a   hordókban   található   benzin
  142.           összmennyisége  pontosan  a  teljes  körutazás  megtételéhez
  143.           szükséges adaggal egyezik  meg. A gépkocsi  tankja rugalmas:
  144.           mindig  képes  befogadni  az  aktuális  hordó  tartalmát.  A
  145.           feladat  annak   meghatározása,  hogy   a  (kezdetben   üres
  146.           tartályú) autó hol kezdje útját, s milyen irányban haladjon.
  147.  
  148.           Beküldési határidô: 1995. augusztus 30.
  149.